package com.yulan.dp.string;

import org.junit.Test;

/**
 * 最长公共子序列
 */
public class LCS {
    public int ReLCS(String a, String b, int i , int j){
        if(i == -1 || j == -1) return 0;

        if(a.charAt(i) == b.charAt(j)) return ReLCS(a,b,i-1,j-1) + 1;

        else
            return Math.max(ReLCS(a,b,i-1,j), ReLCS(a,b,i,j-1));
    }

    public int DpLCS(String a, String b){
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                if(a.charAt(i-1) == b.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[n][m];
    }


    @Test
    public void test(){
        String a = "abcde", b = "ace";
//        System.out.println(ReLCS(a,b,a.length()-1,b.length()-1));
        System.out.println(DpLCS(a,b));
    }
}
